求和 (sum) 的题解

题目背景

AC_Automation 作为一个可爱的妹子，她喜欢求和而不喜欢乘积。她现在有一个序列，想让你求一些东西。看在她那么可爱的份上，就帮帮她吧。

题目描述

为了让你解出题目，善良的她定义了两个函数： $f(l, r)$ 和 $g(l, r)$ ，满足：

$f(l, r) = \sum^{r}_{i = l} A_i = A_l + A_{l + 1} + ... \text{ +} A_r$

$g(l, r) = \sum_{l \le i \le j \le r} f(i, j)$

（例如：$g(1, 3) = f(1, 1) + f(1, 2) + f(1, 3) + f(2, 2) + f(2, 3) + f(3, 3)$）

现在她给了你一个长度为 $n$ 的序列 $A_n$ ，以及 $T$ 个询问，对于第 $i$ 个询问 $l_i, r_i$ ，请你求出对应的 $g(l_i, r_i)$

由于她太菜了，看在她那么可爱的份上，就帮帮她吧。

输入格式

第一行两个整数 $n$ 和 $T$ ，分别表示序列长度和询问的个数

第二行 $n$ 个正整数 $A_i$ ，表示 AC_Automation 给你的一个序列。

接下来 $T$ 行，每行一个 $l_i$ 和 $r_i$ ，表示 $T$ 个询问。

输出格式

$T$ 行，表示每个 $l_i$ 和 $r_i$ 所对应的 $g(l_i, r_i)$

样例输入

3 3
1 2 3
1 2
1 3
2 3

样例输出

6
20
10

提示说明

【数据范围与约定】

对于 $100\%$ 的数据，$1 \le n\le 10^6$，$1 \le T\le 10^6$，$1 \le A_i \le 32$。

题解

首先，很显然我们可以去算每个数的贡献，算得：

$g(l, r) = \sum^{r}_{i = l} (i - l + 1) \cdot (r - i + 1) \cdot A_i$

我们用 $2$ 种方法来解这道题：

第一种，整体法 (by 2x6_81)

在开始这个方法之前，先定义一个东西叫做“在 $l \sim r$ 之间的贡献三角形”。如下图所示：

以 $l = 5, r = 8$ 为例：

可以发现，将每一列的数乘起来再求和就是答案。例如上表，$g(5, 8) = (4) \cdot A_5 + (3 + 3) \cdot A_6 + (2 + 2 + 2) \cdot A_7 + (1 + 1 + 1 + 1) \cdot A_8$ 。

以 $n = 7$ 为例，我们先求出 $1 \sim 7$ 的贡献三角形：

假设我们要求出 $l = 3, r = 5$ 时的结果，也就是 $3 \sim 5$ 的贡献三角形，就可以这么求：

第一步，求出 $1 \sim 7$ 的贡献三角形中的前 $5$ 列，如下图所示：

第二步，求出 $1 \sim 7$ 的贡献三角形中的第 $3 \sim 5$ 列，如下图所示：

可以发现，前两步所用的东西是可以通过预处理 $(n + 1 - i) \cdot i \cdot A_i$ 的前缀和得到。

第三步，三角形只保留 $3$ 行 $3$ 列，如下图所示：

这里可以通过减去一个 $\sum^{5}_{i = 3} 2 \cdot (8 - i) \cdot A_i$ 得到该结果，可以发现，这个东西可以通过预处理 $A_i$ 和 $(n - i) \cdot A_i$ 的前缀和得到。

最后一步，将每个数减掉 $2$ ，如下图所示：

这里可以通过减去一个 $\sum^{5}_{i = 3} 2 \cdot (i - 2) \cdot A_i$ 得到该结果，可以发现，这个东西可以通过预处理 $A_i$ 和 $i \cdot A_i$ 的前缀和得到。

综上，可以发现答案是：

$\sum^{r}_{i = l} (n + 1 - i) \cdot i \cdot A_i - (l - 1) \cdot \sum^{r}_{i = l} (n + 1 - i) \cdot A_i - (n - r) \cdot \sum^{r}_{i = l} (i - l + 1) \cdot A_i$

通过预处理 $(n + 1 - i) \cdot i \cdot A_i$ 、$i \cdot A_i$ 、$(n - i) \cdot A_i$ 和 $A_i$ 的前缀和即可

将其暴力拆开，得到：

$\sum^{r}_{i = l} ((n + 1 - i) \cdot i - (l - 1) \cdot (n + 1 - i) - (n - r) \cdot (i - l + 1)) \cdot A_i$

$= \sum^{r}_{i = l} (n \cdot i + i - i^2 - l \cdot n - l + l \cdot i + n + 1 - i - n \cdot i + n \cdot l - n + r \cdot i - r \cdot l + r) \cdot A_i$

$= \sum^{r}_{i = l} (- i^2 - l + l \cdot i + 1 + r \cdot i - r \cdot l + r) \cdot A_i$

$= \sum^{r}_{i = l} (- i^2 + l \cdot i + r \cdot i - r \cdot l - l + r + 1) \cdot A_i$

$= \sum^{r}_{i = l} (- i^2 + (l + r) \cdot i - (r + 1) \cdot (l - 1)) \cdot A_i$

预处理 $-i^2 \cdot A_i$ 、$i \cdot A_i$ 和 $A_i$ 的前缀和即可

第二种，隔离法 (by registerGen)

这个方法非常简单，我们对于每个 $A_i$ 的贡献进行分解，得到如下变换：

$\sum^{r}_{i = l} (i - l + 1) \cdot (r - i + 1) \cdot A_i = \sum^{r}_{i = l} (-i^2 + (l + r) \cdot i + (r + 1) \cdot (-l + 1)) \cdot A_i$

预处理 $-i^2 \cdot A_i$ 、$i \cdot A_i$ 和 $A_i$ 的前缀和即可